#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>

using namespace std;

class Solution {
    vector<int> tmp;
public:
    void merge_sort(vector<int>& nums, int left, int right) {
        if (left == right) return;

        int mid = (left + right) >> 1;// (left+right)/2
        merge_sort(nums, left, mid);
        merge_sort(nums, mid + 1, right);

        int li = left, ri = mid + 1, i = 0;
        while (li <= mid && ri <= right) {
            tmp[i++] = nums[li] < nums[ri] ? nums[li++] : nums[ri++];
        }
        while (li <= mid) {
            tmp[i++] = nums[li++];
        }
        while (ri <= right) {
            tmp[i++] = nums[ri++];
        }

        for (int cur = left; cur <= right; cur++) {
            nums[cur] = tmp[cur - left];
        }
    }
    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size());
        merge_sort(nums, 0, nums.size() - 1);
        return nums;
    }
};